Over generic group $G$, an adversary is given $g \in G$ and $g^n$ where $n \in \mathbb{Z}$ and has to compute $n$.

Hardness depends on your group and how it’s represented.

Attacks

• Index Calculus: $L(\frac{1}{2}, \sqrt{2})$ - only works in $\mathbb{Z}/P$
• Pohlig Hellman: $O(\sqrt{l})$ where $l$ is the largest prime factor of $p$
• Pollard-Rho: $O(\sqrt{p})$
• Baby-Step Giant-Step: $O(\sqrt{p})$